package leetcode.offer;

/**
 * ClassName: Offer13_MovingCount
 * Description: leetcode-剑指offer 13 机器人的运动范围
 * date: 2021-11-09 14:36
 *
 * @author liyifan
 */
public class Offer13_MovingCount {

    int m;

    int n;

    int k;

    boolean[][] visited;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0);
    }

    public int dfs(int i, int j){
        if (i >= m || j >= n || visited[i][j] || check(i, j)) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(i + 1, j) + dfs(i , j + 1);
    }

    public boolean check(int i, int j) {
        int res = 0;
        int l_i = i % 10;
        int h_i = i / 10;
        res = res + l_i + h_i;

        int l_j = j % 10;
        int h_j = j / 10;
        res = res + l_j + h_j;
        return res > k;
    }

    //todo 用bfs试试
}
